package com.mypaper.schedule;

import com.mypaper.dag.DAG;
import com.mypaper.elem.LinkedListNode;
import com.mypaper.elem.PairElement;
import com.mypaper.elem.ScheduleElement;
import com.mypaper.elem.ScheduleNode;
import com.mypaper.elem.TaskAttribute;
import com.mypaper.elem.TaskNode;
import com.mypaper.list.IdleList;
import com.mypaper.list.ScheduleResults;


public class MMSchedule{
	public ScheduleResults scheduleResults;
	public IdleList[] idleTimeList;
	public ScheduleElement[] procFixedCopy;
	public ScheduleResults[] allProcPerTask;
	private ScheduleResults[] origResultsPerProc;
	
	public MMSchedule(DAG dag){
		scheduleResults=new ScheduleResults();
		idleTimeList=new IdleList[dag.procNum];//每个处理器一个空闲时间块列
		for(int i=0; i<dag.procNum; i++){
			idleTimeList[i]=new IdleList();
			idleTimeList[i].insertNode(new PairElement(0,Float.MAX_VALUE));
		}
		procFixedCopy=new ScheduleElement[dag.vertexNum];//记录fixed copy所在的处理器
		allProcPerTask=new ScheduleResults[dag.vertexNum];//record all processors having copies of each task
		for(int i=0;i<dag.vertexNum;i++){
			procFixedCopy[i]=new ScheduleElement();
			allProcPerTask[i]=new ScheduleResults();
		}
		origResultsPerProc=new ScheduleResults[dag.procNum];//the original schedule

		for(int i=0;i<dag.procNum;i++){
			origResultsPerProc[i]=new ScheduleResults();
		}
	}
	
	public void phaseFirst(DAG dag){
		float[][] EFT=new float[dag.vertexNum][dag.procNum];//每个任务在遍历每个处理器时计算出的最早结束执行时间
		float[][] EST=new float[dag.vertexNum][dag.procNum];//每个任务在遍历每个处理器时计算出的最早开始执行时间
		float[][] FT=new float[dag.vertexNum][dag.procNum];
		float[][] ST=new float[dag.vertexNum][dag.procNum];
		int[] procToPerTask=new int[dag.vertexNum];
		
		for(int i=0; i<dag.vertexNum; i++){
			procToPerTask[i]=-1;
			for(int j=0; j<dag.procNum; j++){
				EFT[i][j]=Float.MAX_VALUE;
			}
		}
		ScheduleResults[] mixProcPerTask=new ScheduleResults[dag.vertexNum];
		for(int i=0; i<dag.vertexNum; i++){
			mixProcPerTask[i]=new ScheduleResults();
			float minExec=Float.MAX_VALUE;
			for(int j=0; j<dag.procNum; j++){
				if(minExec>=dag.vertexWeight[i][j]){	
					if(minExec>dag.vertexWeight[i][j]){
						minExec=dag.vertexWeight[i][j];
						mixProcPerTask[i]=new ScheduleResults();//置为空
						mixProcPerTask[i].insertNode(new ScheduleElement(i, j, 0, 0));
					}else{
						mixProcPerTask[i].insertNode(new ScheduleElement(i, j, 0, 0));
					}
				}
			}
		}
		
		TaskNode currentTask=dag.prior.first;
		while(currentTask!=null){
			float eftBack=Float.MAX_VALUE;
			int procBack=-1;
			int noTask=currentTask.info.index;//当前处理任务
			ScheduleNode firstProc=mixProcPerTask[noTask].first;
			int noProc=firstProc.info.processorID;
			while(firstProc!=null){
				noProc=firstProc.info.processorID;
				for(int i=0; i<dag.vertexNum; i++){
					if(dag.edgeWeight[i][noTask]>0){//表示是任务noTask的父节点
						if(procToPerTask[i]!=-1){//i已经分配处理器
							if(procToPerTask[i]==noProc){
								EST[noTask][noProc]=Math.max(EST[noTask][noProc], FT[i][procToPerTask[i]]);
							}else{
								EST[noTask][noProc]=Math.max(EST[noTask][noProc], FT[i][procToPerTask[i]]+dag.edgeWeight[i][noTask]);
							}
						}
					}
				}
				EFT[noTask][noProc]=EST[noTask][noProc]+dag.vertexWeight[noTask][noProc];//计算最早结束时间	
				PairElement searchData=new PairElement(EST[noTask][noProc],EFT[noTask][noProc]);//找空闲的任务
				PairElement beFoundData=(PairElement)idleTimeList[noProc].searchIdle(searchData);//找到的空闲快
				EFT[noTask][noProc]=Math.max(EFT[noTask][noProc], beFoundData.start+dag.vertexWeight[noTask][noProc]);
				if(eftBack>EFT[noTask][noProc]){//比较，替换
					eftBack=EFT[noTask][noProc];
					procBack=noProc;//记录执行处理器
				}
				firstProc=firstProc.next;
			}
			
			PairElement searchData=new PairElement(eftBack-dag.vertexWeight[noTask][procBack],eftBack);//找空闲的任务
			PairElement beFoundData=(PairElement)idleTimeList[procBack].searchIdle(searchData);//找到的空闲快
			//System.out.println(beFoundData);
			if(beFoundData!=null){
				idleTimeList[procBack].updataIdleNode(beFoundData, searchData.start, searchData.end);
			}else{
				System.out.println("There is no idle period.");
			}
			ST[noTask][procBack]=eftBack-dag.vertexWeight[noTask][procBack];
			FT[noTask][procBack]=eftBack;//update information
			procToPerTask[noTask]=procBack;
			ScheduleElement insertItem=new ScheduleElement(noTask, procBack, ST[noTask][procBack], FT[noTask][procBack]);
			scheduleResults.insertNode(insertItem);
			currentTask=currentTask.next;
		}
		
		//scheduleResults.print();
	}
	
	public void MM_Algorithm(DAG dag){
		phaseFirst(dag);
		updateInfo(dag);
		phaseSecond(dag);	
	}
	
	public void updateInfo(DAG dag){
		ScheduleNode sNode=scheduleResults.first;
		while(sNode!=null){
			origResultsPerProc[sNode.info.processorID].insertNode(sNode.info);//将调度结果分解到各个处理器单独的调度结果，方便以后查找
			sNode=sNode.next;
		}
		updateAllProc(dag);
		updateFixedCopy(dag);
		updateIdleList(dag);
	}
	
	public void updateIdleList(DAG dag){
		for(int i=0; i<dag.procNum; i++){
			LinkedListNode current=idleTimeList[i].first;
			PairElement currElement;
			LinkedListNode trailCurrent=idleTimeList[i].first;
			while(current!=null){
				currElement=(PairElement)current.info;
				if(current==idleTimeList[i].first && currElement.start==currElement.end){
					idleTimeList[i].first=idleTimeList[i].first.next;
					idleTimeList[i].count--; 
				}else{
					if(currElement.start==currElement.end){
						if(current.info.equals(idleTimeList[i].last.info)){
							idleTimeList[i].last=trailCurrent;
						}
						trailCurrent.next=current.next;
						current=trailCurrent;
						idleTimeList[i].count--;
					}	
				}
				trailCurrent=current;
				current=current.next;
			}	
		}
	}
	
	public void updateAllProc(DAG dag){
		TaskNode currNode=new TaskNode();
		currNode=dag.prior.first;//按优先级队列取任务
		while(currNode!=null){
			TaskAttribute tAttr=currNode.info;
			int taskSN=tAttr.index;//get the number of current task
			for(int i=0;i<dag.procNum;i++){
				if(origResultsPerProc[i].isfindTask(taskSN)==true){
					ScheduleElement sElement=origResultsPerProc[i].findTask(taskSN);
					allProcPerTask[taskSN].insertNode(sElement);//插入调度的结点，并判断FT
				}
			}//搜索一次schedule，为currTask找fixed copy and all processors
			currNode=currNode.next;
		}//搜索所有的tasks
	}
	
	public void updateFixedCopy(DAG dag){
		for(int i=1; i<dag.vertexNum; i++)
			procFixedCopy[i]=new ScheduleElement(0, 0, 0, 0);
		float[] minFT=new float[dag.vertexNum];		
		TaskNode currNode=new TaskNode();
		currNode=dag.prior.first;//按优先级队列取任务
		while(currNode!=null){
			TaskAttribute tAttr=currNode.info;
			int taskSN=tAttr.index;//get the number of current task
			
			minFT[taskSN]=Float.MAX_VALUE;
			for(int i=0;i<dag.procNum;i++){
				if(origResultsPerProc[i].isfindTask(taskSN)==true){
					ScheduleElement sElement=origResultsPerProc[i].findTask(taskSN);
					if(sElement.endTime<minFT[taskSN]){
						minFT[taskSN]=sElement.endTime;
						procFixedCopy[taskSN].setNum(taskSN, sElement.processorID, sElement.startTime, sElement.endTime);
					}
				}
			}//搜索一次schedule，为currTask找fixed copy and all processors
			currNode=currNode.next;
		}//搜索所有的tasks
	}
	
	public void phaseSecond(DAG dag){
		
		boolean[] isNoChild=new boolean[dag.vertexNum];
		for(int i=0; i<dag.vertexNum; i++){//判断任务是否有孩子
			isNoChild[i]=true;
			for(int j=0; j<dag.vertexNum; j++){
				if(dag.edgeWeight[i][j]>0)
					isNoChild[i]=false;
			}
		}
		boolean[] isNoParent=new boolean[dag.vertexNum];
		for(int i=0; i<dag.vertexNum; i++){//判断任务是否有孩子
			isNoParent[i]=true;
			for(int j=0; j<dag.vertexNum; j++){
				if(dag.edgeWeight[j][i]>0)
					isNoParent[i]=false;
			}
		}
		//确定每个任务的孩子结点的执行情况
		ScheduleResults[] allChildrenPerTask=new ScheduleResults[dag.vertexNum];
		for(int i=0; i<dag.vertexNum; i++){
			allChildrenPerTask[i]=new ScheduleResults();
		}
		ScheduleNode sNode=scheduleResults.first;
		while(sNode!=null){
			for(int j=0; j<dag.vertexNum; j++){
				if(dag.edgeWeight[j][sNode.info.taskID]>0){
					allChildrenPerTask[j].insertNode(sNode.info);
				}
			}
			//将调度结果分解到各个处理器单独的调度结果，方便以后查找
			sNode=sNode.next;
		}
		
		float[][] est=new float[dag.vertexNum][dag.procNum];		
		float[][] ast=new float[dag.vertexNum][dag.procNum];
		
		TaskNode currentTask=dag.prior.first;
		while(currentTask!=null){
			int indexTask=currentTask.info.index;	
			ScheduleElement backOrinElement=scheduleResults.findTask(indexTask);
			if(allChildrenPerTask[indexTask].count>=1){//有至少两个孩子结点，有复制的必要
				ScheduleNode currChild=allChildrenPerTask[indexTask].first;
				int indexProc;
				PairElement foundIdle=new PairElement();
			
				while(currChild!=null){
					indexProc=currChild.info.processorID;//孩子结点所在的处理器
					if(indexProc!=backOrinElement.processorID){
						est[indexTask][indexProc]=calcEST(dag, indexTask, indexProc, est, isNoParent);
						foundIdle=calcAST(indexTask, indexProc, est[indexTask][indexProc], idleTimeList[indexProc], dag);//寻找空闲快，即实际开始时间
						ast[indexTask][indexProc]=Math.max(est[indexTask][indexProc], foundIdle.start);
						
						est[indexTask][indexProc]=calcEST(dag, indexTask, indexProc, est, isNoParent);
						if(ast[indexTask][indexProc]+dag.vertexWeight[indexTask][indexProc]<currChild.info.startTime){//判断是否能让孩子结点前移
							//将所有的孩子结点前移
							ScheduleElement insertItem=new ScheduleElement(indexTask, indexProc, ast[indexTask][indexProc], ast[indexTask][indexProc]+dag.vertexWeight[indexTask][indexProc]);
							scheduleResults.insertNode(insertItem);
							origResultsPerProc[indexProc].insertNode(insertItem);
							allProcPerTask[indexTask].insertNode(insertItem);
							idleTimeList[indexProc].updataIdleNode(foundIdle, ast[indexTask][indexProc], ast[indexTask][indexProc]+dag.vertexWeight[indexTask][indexProc]);
							phaseMove(dag, isNoParent);
						}
					}
					//scheduleResults.print();
					currChild=currChild.next;
				}
			}
			//判断原版本是否可以删除，即判断其他的版本是否能提供所有孩子任务的数据
			updateFixedCopy(dag);
			
			boolean flagDele=true;
			flagDele=isDeleted(backOrinElement, dag);
			if(flagDele==false){
				scheduleResults.insertNode(backOrinElement);//如果不能删除，则还原任务
				origResultsPerProc[backOrinElement.processorID].insertNode(backOrinElement);
				allProcPerTask[backOrinElement.taskID].insertNode(backOrinElement);
				PairElement searchElement=(PairElement)idleTimeList[backOrinElement.processorID].searchIdle(new PairElement(backOrinElement.startTime,backOrinElement.endTime));
				idleTimeList[backOrinElement.processorID].updataIdleNode(searchElement, backOrinElement.startTime,backOrinElement.endTime);
				updateFixedCopy(dag);
			}
			//scheduleResults.print();
			currentTask=currentTask.next;
		}
		scheduleResults.print();
	}
	
	
	public boolean isDeleted(ScheduleElement deleteElement, DAG dag){
		//判断某原版本是否可以删除
		boolean flag=true;
		//首先删除该原版本任务
		int beFoundTask=deleteElement.taskID;
		scheduleResults.deleteNode(deleteElement);
		origResultsPerProc[deleteElement.processorID].deleteNode(deleteElement);
		allProcPerTask[deleteElement.taskID].deleteNode(deleteElement);
		idleTimeList[deleteElement.processorID].insertNode(new PairElement(deleteElement.startTime,deleteElement.endTime));
		updateFixedCopy(dag);
		if(procFixedCopy[deleteElement.taskID].startTime==procFixedCopy[deleteElement.taskID].endTime){
			flag=false;
		}else{
			//判断其他任务是否满足约束关系，如果不满足，flag置为false，表示原版本不可以删除
			for(int i=0; i<dag.procNum; i++){//对每个处理器上的每个孩子任务，判断是否满足约束关系
				ScheduleNode currNode=origResultsPerProc[i].first;
				ScheduleElement foundCopySameProc=origResultsPerProc[i].findTask(beFoundTask);//找是否在当前处理器上存在目标任务
				while(currNode!=null){
					//孩子结点；
					ScheduleElement currTask=currNode.info;		
					if(dag.edgeWeight[deleteElement.taskID][currTask.taskID]>0){
						if(foundCopySameProc==null || foundCopySameProc.endTime > currTask.startTime){//没有本地父节点或者在当前任务之后，则判断能否由fixed copy提供数据
							if(procFixedCopy[beFoundTask].endTime+dag.edgeWeight[beFoundTask][currTask.taskID]>currTask.startTime){
								flag=false;
							}
						}
						
					}
					currNode=currNode.next;
				}
			}
		}
		
		return flag;
	}
	
	public void phaseMove(DAG dag, boolean[] isNoParent){
		float aest;
	
		float[][] est=new float[dag.vertexNum][dag.procNum];		
		TaskNode currNode=dag.prior.first;
		PairElement foundIdle=new PairElement();
		while(currNode!=null){
			updateIdleList(dag);
			TaskAttribute tAttr=currNode.info;
			int taskSN=tAttr.index;//get the number of current task
			//if(allProcPerTask[taskSN].count>1){
				ScheduleNode tempNode=allProcPerTask[taskSN].first;//获得当前任务的第一个处理器情况结点
				while(tempNode!=null){
					ScheduleElement tempElement=(ScheduleElement)tempNode.info;
					int procSN=tempElement.processorID;
					ScheduleElement changeNode=tempElement.getCopy();
					est[taskSN][procSN]=calcEST(dag, taskSN, procSN, est, isNoParent);
					scheduleResults.deleteNode(taskSN);
					idleTimeList[procSN].insertNode(new PairElement(tempElement.startTime, tempElement.endTime));
					foundIdle=calcAST(taskSN, procSN, est[taskSN][procSN], idleTimeList[procSN], dag);
					aest=Math.max(est[taskSN][procSN], foundIdle.start);
					ScheduleElement insertItem=new ScheduleElement(taskSN, procSN, aest, aest+dag.vertexWeight[taskSN][procSN]);
					scheduleResults.insertNode(insertItem);
					idleTimeList[procSN].updataIdleNode(foundIdle, aest, aest+dag.vertexWeight[taskSN][procSN]);
					allProcPerTask[taskSN].updateNode(changeNode, aest, aest+dag.vertexWeight[taskSN][procSN]);//update 
					origResultsPerProc[procSN].updateNode(changeNode, aest, aest+dag.vertexWeight[taskSN][procSN]);
					tempNode=tempNode.next;
				}
			//}//
			currNode=currNode.next;
		}
		updateFixedCopy(dag);
		
		/*for(int i=0; i<taskNum; i++){
			System.out.println("Task "+i+":"+procFixedCopy[i]);	
		}*/
	}
	
	public float calcEST(DAG dag, int indexTask, int indexProc, float[][] est, boolean[] isNoParent){		
		updateFixedCopy(dag);		
		est[indexTask][indexProc]=0;
		if(isNoParent[indexTask]==true){
			est[indexTask][indexProc]=0;
		}else{
			for(int j=0; j<dag.vertexNum; j++){
				if(dag.edgeWeight[j][indexTask]!=0){//is a parent of task
					//calculate the earliest start time of all copies of parents and shift tasks	
					ScheduleElement localCopy=origResultsPerProc[indexProc].findTask(j);//父节点在本地的版本
					ScheduleElement fixedCopy=procFixedCopy[j];//FixedCopy
					if(localCopy!=null){
						est[indexTask][indexProc]=Math.max(est[indexTask][indexProc], Math.min(localCopy.endTime, fixedCopy.endTime+dag.edgeWeight[j][indexTask]));
					}else{
						est[indexTask][indexProc]=Math.max(est[indexTask][indexProc], fixedCopy.endTime+dag.edgeWeight[j][indexTask]);
					}
				}
			}
			//计算当前任务的EST及AST
		}
		return est[indexTask][indexProc];
	}

	public PairElement calcAST(int indexTask, int indexProc, float estCurr, IdleList idleLists, DAG dag){
		PairElement findElement=new PairElement(Float.MAX_VALUE, Float.MAX_VALUE);//找到一个满足条件的最大的空闲块
		LinkedListNode currNode=idleLists.first;
		while(currNode!=null){
			PairElement pElement=(PairElement)currNode.info;
			if(pElement.end>=Math.max(estCurr, pElement.start)+dag.vertexWeight[indexTask][indexProc]){		
				if(pElement.start<findElement.start)
					findElement.setNum(pElement.start, pElement.end);
			}
			currNode=currNode.next;
		}
		
		//idleLists.updataIdleNode(findElement,ast,ast+dag.vertexWeight[indexTask][indexProc]);
		return findElement;
	}
	
	public float energyCal(int procNum){
		float enerSum=0;
        float timeSum=0;	
        float totalTime=0;
        float power=(float)0.925, idlePower=(float)0.260;
        boolean[] flag=new boolean[procNum];
        float[] procTermTime=new float[procNum];
        ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			ScheduleElement perTask=currentTask.info;
			if(flag[perTask.processorID]!=true)
				flag[perTask.processorID]=true;
			if(perTask.endTime>procTermTime[perTask.processorID])
				procTermTime[perTask.processorID]=perTask.endTime;
			timeSum+=(perTask.endTime-perTask.startTime);
			currentTask=currentTask.next;
		}
		
		for(int i=0; i<procNum; i++){
			System.out.println("End time of processor "+i+" is "+procTermTime[i]);
			totalTime+=procTermTime[i];
		}
		System.out.println("idletime： "+(totalTime-timeSum));
		System.out.println("busytime： "+timeSum);
		enerSum=timeSum*power+(totalTime-timeSum)*idlePower;
		return enerSum;
	}
	
	
	public float makespan(){
		float curr=0;
		ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			if(curr<currentTask.info.endTime)
				curr=currentTask.info.endTime;
			currentTask=currentTask.next;
		}
		return curr;
	}
	
	public float timeCal(int procNum){
        float timeSum=0;	
        float totalTime=0;
        boolean[] flag=new boolean[procNum];
        float[] procTermTime=new float[procNum];
        ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			ScheduleElement perTask=currentTask.info;
			if(flag[perTask.processorID]!=true)
				flag[perTask.processorID]=true;
			if(perTask.endTime>procTermTime[perTask.processorID])
				procTermTime[perTask.processorID]=perTask.endTime;
			timeSum+=(perTask.endTime-perTask.startTime);
			currentTask=currentTask.next;
		}
		
		for(int i=0; i<procNum; i++){
			System.out.println("End time of processor "+i+" is "+procTermTime[i]);
			totalTime+=procTermTime[i];
		}
		System.out.println("idletime： "+(totalTime-timeSum));
		System.out.println("busytime： "+timeSum);
		return timeSum;
	}
}
